Subject: Re: your mail

From: [email-masked] (Ariel Orda)
Date: Mon, 5 May 1997 15:21:54 +0300

Masataka,

  >The problem is that the aggregation makes a single aggregated
  >router have multiple internal hops.
  >
  >That is, the assumption that "certain types of schedulers
  >are used in the network" is no longer valid.
  >
As I said in a previous note, "In our view, this simple solution is still 
unsatisfactory and calls for additional work." However, a long journey 
begins with a first step, which in our case is that of considering the 
scenario where the path selection process has an exact image of the topology, 
as done in [GO96] (deterministic case), [GOW], [CCS] and [MaSt] (see 
references in my former note). In [GO96] we considered also more complex 
scenarios.

  >> The result 
  >> is that while there is clearly an increase in complexity because
  >> of the *uncertainty* introduced by the aggregation process, it is
  >> still possible to devise tractable solutions under relatively 
  >> reasonable assumptions (see [GO96] for details).
  >
  >It's not uncertainity, at all.
  >
  >
  >Aggregation naturally brings in inaccuracy, which is unavoidable
  >but NOT a problem here.
  >
Well, when the information is "inaccurate", the path selection process faces
"uncertainty". While this inaccuracy/uncertainty might not be the only problem, 
it is certainly A problem.
 
  >> Again, see [GO96] for some possible approaches on how to handle
  >> such cases.
  >
  >Of course, it may not be impossible to approximate any scheduler
  >used with P.NNI consists of integral number of cascaded WFQ-type
  >schedulers and have some approximated algorithm which have
  >complexity polynominal to N, where N is the number of all the
  >cascaded WFQs.
  >
  >But, it is just yet another approximation algorithm and N could be
  >very large to be impractical.
  >
A main purpose of [GS96] was precisely to struggle with such questions, i.e.,
to see when and how an efficient solution, either exact or approximated, can
be found. Except for the specific solutions presented there, we believe that
that study offers a framework and insight for additional related results,
some of which are currently under investigation.

  >
  >Qingming successfully showed a way to know an existence of a path
  >to satisfy QoS requirement.
  >
OK, this is what I meant.

 >
  >As long as you use the bandwidth actually used for the computation,
  >yes, the path found is optimal w.r.t. the bandwidth.
  >
  >But, as we use minimal bandwidth to satisfy the requirement,
  >the once-shortest path may not be the shortest (shortest delay,
  >for example) with reduced bandwidth and modified cost function.
  >
An easy way to accommodate your point, namely finding the path
that satisfies the delay constraint with the minimum bandwidth, can be
found as follows, using the standard approach presented in the above 
studies. 

(1) Execute the Bellman-Ford algorithm for all (up to M) bandwidth/rate 
values.

(2) In each execution, record the shortest path (w.r.t. the "constant 
delays" metric of each link) for each possible hop count.

This results in a total of O(M*H) paths, where H=<the network
diameter. 

(3) Check then the best end-to-end bound for each path, and discard
those that do not meet the delay constraint. Note that in the case
of the GS model, this means computing the end-to-end delay bound
on each path assuming the (maximum) bandwidth value B_m used in the
execution of the Bellman-Ford algorithm during which the path was
computed.

(4) For each remaining path, choose the minimum possible bandwidth to 
be consumed (on all links of the path) such that the delay constraint 
remains satisfied (note that the consumed bandwidth is no more, and 
typically less, than B_m).

(5) Now choose the path with the minimal bandwidth. 

It is easily shown that the chosen path has the minimal bandwidth among 
those that can satisfy the delay constraint. Moreover, the above scheme 
can be adapted to solve the following, more general problem. Suppose we 
look for the path with the minimal "cost" among those that satisfy the 
delay constraint, and assume that the cost of a path is some general, 
nondecreasing function of (1) the number of hops, (2) the consumed 
bandwidth and (3) the end-to-end delay (or its corresponding upper-bound). 
For example, the case we handled above is accommodated by defining the 
cost to be equal to the consumed bandwidth; alternatively, one might want 
to minimize the networkwide consumption of bandwidth, which is accommodated 
by defining the cost as (consumed bw * number of hops). A solution to this, 
more general problem can be found by applying the above scheme, but with 
the following modified steps (4), (5):

(4) For each remaining path, choose the bandwidth to be consumed (on all
links of the path) such that the delay constraint remains satisfied and
*the cost of the path is minimized* (again, the consumed bandwidth is no 
more, and typically less, than B_m).

(5) Now choose the path with *the minimal cost*. 

It can be shown that the chosen path indeed has the minimal cost
among those that can satisfy the delay constraint.

Ariel

---

From: Masataka Ohta <[email-masked]>
Date: Thu, 8 May 97 12:48:27 JST

Ariel;

> begins with a first step,

There are a lot of first steps of a lot of journeys.

The problem is that few of them, if any, is connected to the last step
to the destinaiton.

> which in our case is that of considering the 

Can you show me the reference to [Go96] again?

The working group, surprisingly, has no official ftp log site.

> "uncertainty".

What, do you mean, "uncertainity" is?

With moderate underestimation of resource, we can "certainly" find
a path without cranking back operations.

Then, there is a possibility that a certain path can not be found,
becasue of underestimated aggregated resource, which is not a
problem.

Of course, there can be transient uncertainity even if we don't
aggregate. But, simple retry can get around it.

> An easy way to accommodate your point,

You are brighter than Qingming.

> namely finding the path

Sorry, but, your modification does not work.

> (1) Execute the Bellman-Ford algorithm for all (up to M) bandwidth/rate 

OK.

> delays" metric of each link) for each possible hop count.

No. The Bellman-Ford algorithm finds a best path with no more,
hop count than, but not necessarily equal to, the current hop
limit.

							Masataka Ohta